package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class _85_MaximalRectangle {
    public static void main(String[] args) {
        Solution solution = new _85_MaximalRectangle().new Solution();
        char[][] matrix = new char[][]{{'0', '1'}, {'1', '0'}};
        int i = solution.maximalRectangle(matrix);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        private int largestRectangleArea(int[] heights) {
            int res = 0;
            Deque<Integer> stack = new LinkedList<>();
            int[] new_heights = new int[heights.length + 2];
            for (int i = 1; i < heights.length + 1; i++) {
                new_heights[i] = heights[i - 1];
            }
            for (int i = 0; i < new_heights.length; i++) {
                while (!stack.isEmpty() && new_heights[stack.peek()] > new_heights[i]) {
                    int cur = stack.pop();
                    int l = stack.peek();
                    int r = i;
                    res = Math.max(res, (r - l - 1) * new_heights[cur]);
                }
                stack.push(i);
            }
            return res;
        }

        public int maximalRectangle(char[][] matrix) {
            if (matrix.length == 0) return 0;
            int m = matrix.length, n = matrix[0].length, res = 0;
            int[] line = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0) {
                        line[j] = matrix[i][j] == '0' ? 0 : 1;
                    } else {
                        line[j] = matrix[i][j] == '0' ? 0 : line[j] + 1;
                    }
                }
                res = Math.max(res, largestRectangleArea(line));
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}